﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //同余定理
    //k的倍数
    //a % k = x,b % k = y
    //(a + b) % k == 0 -> (x + y) % k == 0
    //动态规划：dp[i][j]表示在前i个数字选择，总和%k为j的最大值
    //动态转移方程：dp[i][j] = max(dp[i - 1][j],dp[i - 1][(j - a[i] % k + k) % k] + a[i])
    //解释：如果不选择a[i]的话，dp[i][j] = dp[i - 1][j]
    //如果选择a[i]的话，因为总和%k要等于j，根据同余定理，要选择j - a[i] % k
    //如果j - a[i] % k大于0，那么正常选择
    //如果j - a[i] % k小于0，那么要处理越界
    //加上k，比如，j = 2，a[i] = 8，k = 5
    //a[i] % k = 3,j - 3 = -1
    //加上k为4
    //也就是(4 + 3) % k = 2，即等于j
    //但是在大于0的情况下，加上k会错误，比如原本需要余数是1，再加上k为5，为6，再%k变为了1
    //初始化：dp[0][0] = 0 即%k为0，那么不选择数字即可，所以总和为0
    //dp[0][j] (j > 0) 没有数字可以选择，但是要%k要为j，非法值，全部初始为负数
    //填表顺序：从左往右，从上到下
    //返回值：dp[n][0]
    long long n, k;
    cin >> n >> k;

    vector<long long> vec(n + 1, 0);
    for (long long i = 1; i < n + 1; ++i)
    {
        cin >> vec[i];
    }

    vector<vector<long long>> dp(n + 1, vector<long long>(k, 0));
    for (long long j = 1; j < k; ++j)
    {
        dp[0][j] = -0x3f3f3f3f3f3f3f3f;
    }

    for (long long i = 1; i < n + 1; ++i)
    {
        for (long long j = 0; j < k; ++j)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - vec[i] % k + k) % k] + vec[i]);
        }
    }

    if (dp[n][0] <= 0)
        cout << -1 << endl;
    else
        cout << dp[n][0] << endl;
    return 0;
}

/*
小红拿到了一个数组，她想取一些数使得取的数之和尽可能大，
但要求这个和必须是k的倍数。
你能帮帮她吗？
输入描述：
第一行输入两个正整数n和k第二行输入n个正整数ai
​，1≤n,k≤10^3，1≤ai≤10^10

输出描述：
如果没有合法方案，输出 -1。
否则输出最大的和。

示例1
输入：
5 5
4 8 2 9 1
输出：
20
说明：
取后四个数即可
*/

